package easy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

public class Solution_589 {

    private List<Integer> list = new ArrayList<>();

    public List<Integer> preorder(Node root) {
        Map<Node, Integer> map = new HashMap<>();
        Stack<Node> stack = new Stack<>();
        Node next = root;
        while (!stack.empty() || next != null) {
            if (next!=null) {
                if (!map.containsKey(next)) {
                    list.add(next.val);
                }
                if (next.children != null && next.children.size()>0) {
                    Integer childIndex = map.getOrDefault(next, -1);// 标记当前节前是父节点的第几个子节点
                    if (childIndex+1 < next.children.size()) {
                        childIndex++;
                        map.put(next, childIndex);
                        stack.push(next);
                        next = next.children.get(childIndex);
                    } else {
                        next = null;
                    }
                } else {
                    next = null;
                }
            } else {
                next = stack.pop();
            }
        }
        return list;
    }

    /*public List<Integer> preorder(Node root) {
        if (root != null) {
            dps(root);
        }
        return list;
    }*/

    private void dps(Node node) {
        list.add(node.val);
        if (node.children != null)
        for (Node child : node.children) {
            dps(child);
        }
    }

    public static void main(String[] args) {
        Solution_589 model = new Solution_589();
        Node node = new Node(1);

        Node node1 = new Node(3);
        Node node2 = new Node(2);
        Node node3 = new Node(4);
        List<Node> list = new ArrayList<>();
        list.add(node1);
        list.add(node2);
        list.add(node3);
        node.children = list;

        Node node4 = new Node(5);
        Node node5 = new Node(6);

        List<Node> list1 = new ArrayList<>();
        list1.add(node4);
        list1.add(node5);
        node1.children = list1;

        System.out.println(model.preorder(node));
    }

    static class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    };
}
